package Algorithms.classic;

/**
 * description: <br>
 * createTime: 2020/8/1415:16 <br>
 *
 * @author zzh
 */
public class QuickSortLeft {

    public static void main(String[] args) {
        SortUtils.test(QuickSortLeft::quickSort);
    }


    private static int[] quickSort(int[] array) {
        quickSort(array, 0, array.length - 1);
        return array;
    }


    private static void quickSort(int[] array, int left, int right) {
        if(right <= left) {
            return;
        }
        int qivot = array[left];
        int mid = partitionIt(array, left, right, qivot);
        quickSort(array, left, mid - 1);
        quickSort(array, mid + 1, right);
    }


    private static int partitionIt(int[] array, int left, int right, int qivot) {
        int leftIndex = left;
        int rightIndex = right + 1;
        while(true) {
            while(leftIndex < right && array[++leftIndex] < qivot) {}
            while(array[--rightIndex] > qivot) {}
            if(rightIndex <= leftIndex) {
                break;
            }
            SortUtils.swap(array, leftIndex, rightIndex);
        }
        SortUtils.swap(array, left, rightIndex);
        return rightIndex;
    }
}
